#include<iostream>
#include <fstream>
#include<cstdlib>
#include<vector>
#include<queue>
#include<string>
#include<cstdio>
#include<cmath>

using namespace std;

#define forn(i,n) for(typeof(n) i=0;i<(n);i++)
#define forsn(i,s,n) for(typeof(n) i=s;i<(n);i++)
#define forall(it,X) for( typeof((X).begin()) it = (X).begin() ; it!=(X).end() ; it++ )
#define inf 2147483647
#define STRENGTH 0.2 

typedef vector<bool> vbool;
typedef vector<string> vstring;
typedef vector<int> vint;
typedef vector<vint> vvint;

struct selected_words{
	int positive;
	int negative;
	int neutral;
};

int binarySearch(int, vstring, string);
vint dijkstra(int, vvint, int);
selected_words  chooseWords(int, vstring, vvint, vint);
template<typename T> void printMatrix(int, vector< vector<T> >);
template<typename T> void printVector(int, vector<T>);

int main(int argc, char** argv){
	if(argc==3){
		int n;
		
		//Abro el archivo que tiene la lista de adjetivos
		ifstream adjectives(argv[1]);
		if(!adjectives.is_open()) cout << "No se puedo abrir el archivo: " << argv[1] << endl;
		adjectives >> n;
		vstring words(n);
		vint freqs(n);
		forn(i,n){
			adjectives >> words[i];
			adjectives >> freqs[i]; 
		}
		adjectives.close();
		printVector(n,words);
		printVector(n,freqs);
		
		//Abro el archivo que tiene los sinonimos
		ifstream synonyms(argv[2]);
		if(!synonyms.is_open()) cout << "No se puedo abrir el archivo: " << argv[2] << endl;
		vvint adjacency(n,vint(n,0));
		int adjective;
		int amount_syn;
		int position_syn;
		forn(i,n){			
			synonyms >> adjective;
			synonyms >> amount_syn;
			forn(j,amount_syn){
				synonyms >> position_syn;
				adjacency[adjective][position_syn]=1;
			}
		}
		synonyms.close();
		printMatrix(n,adjacency);
		
		selected_words sw = chooseWords(n,words,adjacency,freqs);
		cout << "Positiva --> " << words[sw.positive] << endl;
		cout << "Negativa --> " << words[sw.negative] << endl;
		cout << "Neutras --> " << words[sw.neutral] << endl;
	}
	else{
		cout << "USO: ./dijkstra [lista de adjetivos y frecuencias] [grafo de sinonimos]" << endl;
	}
	return 0;
}

/* Precondicion: n>0 y word en el vector */
int binarySearch(int n, vstring words, string word){
	int start=0;
	int end=n-1;
	int middle=(end+start)/2;
	while(words[middle]!=word && start<=end){
		middle=(end+start)/2;
		if(word > words[middle])
			start=middle+1;
		else
			end=middle-1;
	}
	return middle;
}

vint dijkstra(int n, vvint adjacency, int initial){
	vbool out(n,false);
	out[initial]=true;
	vint dist(n,inf);
	dist[initial]=0;
	queue<int> q;
	q.push(initial);
	int new_dist, actual;
	while(!q.empty()){
		actual = q.front();
		q.pop();
		forn(i,n){
			if(adjacency[actual][i]==1){
				new_dist=dist[actual]+1;
				if(new_dist<dist[i])
					dist[i]=new_dist;
				if(!out[i]){
					q.push(i);
					out[i]=true;
				}
			}
		}
	}
	return dist;
}

selected_words  chooseWords(int n, vstring words, vvint adjacency, vint freqs){
	//Busco la distancia de todas las palabras a malo
	int pos_bad = binarySearch(n,words,"malo");
	vint dist_bad(n);
	dist_bad = dijkstra(n,adjacency,pos_bad);
	
	//Busco la distancia de todas las palabras a bueno
	int pos_good = binarySearch(n,words,"bueno");
	vint dist_good(n);
	dist_good = dijkstra(n,adjacency,pos_good);
	
	int pos_neutral = binarySearch(n,words,"neutro");
	
	selected_words sw;
	sw.positive = pos_good;
	sw.negative = pos_bad;
	sw.neutral = pos_neutral;
	int dist_bad_good = dist_bad[pos_good]; //distancia de la palabra malo a bueno
	double so;
	forn(i,n){
		so = (double)(dist_bad[i] - dist_good[i])/dist_bad_good;
		if(abs(so) < STRENGTH){
			if(freqs[sw.neutral]<freqs[i])
				sw.neutral = i;
		}
		else{
			if(so>0){
				if(freqs[sw.positive]<freqs[i])
					sw.positive = i;
			}
			else{
				if(freqs[sw.negative]<freqs[i])
					sw.negative = i;
			}
		}
	}
	return sw;
}

template<typename T>
void printMatrix(int n, vector< vector<T> > matrix){
	forn(i,n){
		forn(j,n)
			cout << matrix[i][j] << "	";
		cout << endl;
	}
}

template<typename T>
void printVector(int n, vector<T> vector){
	forn(i,n)
		cout << vector[i] << "	";
	cout << endl;
}
